package com.leetcode.algorithm.y19.m02;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode-cn.com
 * (TODO)50. Pow(x, n)
 * (done)367. 有效的完全平方数
 * (done)69. x 的平方根
 * (done)633. 平方数之和
 * (done)54. 螺旋矩阵
 * (done)59. 螺旋矩阵 II
 * (done)821. 字符的最短距离
 * @author: jie.deng
 * @time: 2019年2月27日 下午1:50:01
 */
public class MySolution0227 {
	/**
	 * 50. Pow(x, n)
	 * 
     * 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
     * 
     * 示例 1:
     * 
     * 输入: 2.00000, 10
     * 输出: 1024.00000
     * 示例 2:
     * 
     * 输入: 2.10000, 3
     * 输出: 9.26100
     * 示例 3:
     * 
     * 输入: 2.00000, -2
     * 输出: 0.25000
     * 解释: 2-2 = 1/22 = 1/4 = 0.25
     * 说明:
     * 
     * -100.0 < x < 100.0
     * n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
	 * @param x
	 * @param n
	 * @return
	 */
	public double myPow(double x, int n) {
		if (x == 1) {
			return 1;
		}
		if (n == 0) {
			return 1;
		}
		double sum = 1.0d;
		if (n > 0) {
			while (n > 0) {
				sum *= x;
				n--;
			}
		} else {
			if (n == Integer.MIN_VALUE) {
				sum /= x;
				n = Math.abs(n + 1); // 问题在这里,最小值的绝对值溢出了
			} else {
				n = Math.abs(n);
			}
			while (n > 0) {
				sum /= x;
				n--;
			}
		}
		return sum;
	}
    
    /**
     * 367. 有效的完全平方数
     * 
     * 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
     * 
     * 说明：不要使用任何内置的库函数，如  sqrt。
     * 
     * 示例 1：
     * 
     * 输入：16
     * 输出：True
     * 示例 2：
     * 
     * 输入：14
     * 输出：False
     * @param num
     * @return
     */
	public boolean isPerfectSquare(int num) {
		int left = 0;
		int right = num / 2 + 1;
		if (left * left == num || right * right == num) {
			return true;
		}
		int mid = (left + right) / 2; // 考虑left + right溢出的情况
		while (mid < right && mid > left && mid * mid != num) {
			if (mid > num / mid) { // 之前这里写的是 mid*mid > num,没有考虑到mid*mid溢出的情况
				right = mid;
			} else {
				left = mid;
			}
			mid = (left + right) / 2;
		}
		return mid * mid == num;
	}
    
    /**
     * 69. x 的平方根
     * 
     * 实现 int sqrt(int x) 函数。
     * 
     * 计算并返回 x 的平方根，其中 x 是非负整数。
     * 
     * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
     * 
     * 示例 1:
     * 
     * 输入: 4
     * 输出: 2
     * 示例 2:
     * 
     * 输入: 8
     * 输出: 2
     * 说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。
     * @param x
     * @return
     */
	public int mySqrt(int x) {
		int left = 0;
		int right = x / 2 + 1;
		if (left * left == x) {
			return left;
		}
		if (right * right == x) {
			return right;
		}
		int mid = (left + right) / 2;
		while (mid < right && mid > left && mid * mid != x) {
			if (mid > x / mid) { // 之前这里写的是 mid*mid > x,没有考虑到mid*mid溢出的情况
				right = mid;
			} else {
				left = mid;
			}
			mid = (left + right) / 2;
		}
		return mid;
	}
    
    /**
     * 633. 平方数之和
     * 
     * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
     * 
     * 示例1:
     * 
     * 输入: 5
     * 输出: True
     * 解释: 1 * 1 + 2 * 2 = 5
     *  
     * 
     * 示例2:
     * 
     * 输入: 3
     * 输出: False
     */
	public boolean judgeSquareSum(int c) {
		if (c == 0 || c == 1) {
			return true;
		}
		int sqrtR = (int) Math.sqrt(c);
		int sqrtL = (int) Math.sqrt(c / 2);
		for (int i = sqrtL; i <= sqrtR; i++) {
			int diff = c - i * i;
			int sqrt = (int) Math.sqrt(diff);
			if (sqrt * sqrt == diff) {
				return true;
			}
		}
		return false;
	}
    
    /**
     * 54. 螺旋矩阵
     * 
     * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
     * 
     * 示例 1:
     * 
     * 输入:
     * [
     *  [ 1, 2, 3 ],
     *  [ 4, 5, 6 ],
     *  [ 7, 8, 9 ]
     * ]
     * 输出: [1,2,3,6,9,8,7,4,5]
     * 示例 2:
     * 
     * 输入:
     * [
     *   [1, 2, 3, 4],
     *   [5, 6, 7, 8],
     *   [9,10,11,12]
     * ]
     * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
     * @param matrix
     * @return
     */
	public List<Integer> spiralOrder(int[][] matrix) {
		int m = matrix.length;
		if (m == 0) {
			return new ArrayList<Integer>(0);
		}
		int n = matrix[0].length;
		List<Integer> list = new ArrayList<Integer>(m * n);
		int spiral = 0;
		while ((m - spiral * 2) > 0 && (n - spiral * 2) > 0) {
			// 上 row=0,col=[0,n-1]---
			for (int col = spiral; col <= (n - spiral) - 1; col++) {
				list.add(matrix[spiral][col]);
			}
			// 右 row=[1,m-2],col=n-1
			for (int row = 1 + spiral; row <= (m - spiral) - 2; row++) {
				list.add(matrix[row][(n - spiral) - 1]);
			}
			// 下 row=m-1,col=[n-1,0]
			if ((m - spiral) - 1 > spiral) {
				for (int col = (n - spiral) - 1; col >= spiral; col--) {
					list.add(matrix[(m - spiral) - 1][col]);
				}
			}
			// 左 row=[m-2,1],col=0
			if ((n - spiral) - 1 > spiral) {
				for (int row = (m - spiral) - 2; row >= spiral + 1; row--) {
					list.add(matrix[row][spiral]);
				}
			}
			// 下一圈 m = m-1; n=n-1;
			spiral++;
		}
		return list;
	}
    
    /**
     * 59. 螺旋矩阵 II
     * 
     * 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
     * 
     * 示例:
     * 
     * 输入: 3
     * 输出:
     * [
     *  [ 1, 2, 3 ],
     *  [ 8, 9, 4 ],
     *  [ 7, 6, 5 ]
     * ]
     * @param n
     * @return
     */
	public int[][] generateMatrix(int n) {
		int[][] matrix = new int[n][n];
		int spiral = 0;// 螺旋的序号
		int num = 1;
		while (num <= n * n) {
			for (int col = spiral; num <= n * n && col <= (n - spiral) - 1; col++) {
				matrix[spiral][col] = num;
				num++;
			}
			// 右 row=[1,n-2],col=n-1
			for (int row = 1 + spiral; num <= n * n && row <= (n - spiral) - 2; row++) {
				matrix[row][(n - spiral) - 1] = num;
				num++;
			}
			// 下 row=n-1,col=[n-1,0]
			if ((n - spiral) - 1 > spiral) {
				for (int col = (n - spiral) - 1; num <= n * n && col >= spiral; col--) {
					matrix[(n - spiral) - 1][col] = num;
					num++;
				}
			}
			// 左 row=[n-2,1],col=0
			if ((n - spiral) - 1 > spiral) {
				for (int row = (n - spiral) - 2; num <= n * n && row >= spiral + 1; row--) {
					matrix[row][spiral] = num;
					num++;
				}
			}
			spiral++;
		}
		return matrix;
	}
    
    /**
     * 821. 字符的最短距离
     * 
     * 给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
     * 
     * 示例 1:
     * 
     * 输入: S = "loveleetcode", C = 'e'
     * 输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
     * 说明:
     * 
     * 字符串 S 的长度范围为 [1, 10000]。
     * C 是一个单字符，且保证是字符串 S 里的字符。
     * S 和 C 中的所有字母均为小写字母。
     * @param S
     * @param C
     * @return
     */
	public int[] shortestToChar(String S, char C) {
		int[] ret = new int[S.length()];
		// S中第一个字符C左边的字符[fromIdx,idxR]距离为 idxR - i
		int fromIdx = 0;
		int idxR = S.indexOf(C, fromIdx);
		for (int i = fromIdx; i <= idxR; i++) {
			ret[i] = idxR - i;
		}
		// 中间的字符，计算与左右的距离的较小值
		int idxL = idxR;
		fromIdx = idxL + 1;
		while ((idxR = S.indexOf(C, fromIdx)) != -1) {
			for (int i = fromIdx; i <= idxR; i++) {
				ret[i] = Math.min(i - idxL, idxR - i);
			}
			idxL = idxR;
			fromIdx = idxL + 1;
		}
		
		// S中最后一个字符C右边的字符[idxL,S.length())距离为 i - idxL
		for (int i = fromIdx; i <= S.length() - 1; i++) {
			ret[i] = i - idxL;
		}
		return ret;
	}
}
